package 剑指offer;

public class 逆序对 {
    /**
     * 在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。
     * 输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出。
     *  即输出P%1000000007
     * @param args
     */
    /**
     * 对于%50的数据,size<=10^4
     * <p>
     * 对于%75的数据,size<=10^5
     * <p>
     * 对于%100的数据,size<=2*10^5
     */
    public static void print(int[] arr) {
        int count = 0;
        for (int i = 0; i < arr.length; i++) {
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[i] > arr[j]) {
                    count++;
                }
            }
        }
        if (count < Math.pow(10, 4)) {
            System.out.println(count % 50);
        } else if (count < Math.pow(10, 5)) {
            System.out.println(count % 75);
        } else if (count < 2 * Math.pow(10, 5)) {
            System.out.println(count % 100);
        }

    }

    public static int InversePairs(int[] arr) {
        int[] dp = new int[arr.length];
        for (int i = arr.length - 2; i >= 0; i--) {
            if (arr[i] > arr[i + 1]) {
                dp[i] = dp[i + 1] + 1;
            } else {
                int index = i + 1;
                while (index <= arr.length - 1) {
                    if (arr[i] > arr[index]) {
                        dp[i] = dp[index] + 1;
                        break;
                    }
                    index++;
                }
            }
        }
        int count = 0;
        for (int i : dp) {
            count += i;
        }
        System.out.println(count);
        return count;
    }

    static int mod = (int) 1e9 + 7;
    static int count = 0;
    static int[] arr = new int[220000];

    //通过合并排序
    public static void Merge(int l, int mid, int r, int[] array) {
        int i = l, j = mid + 1, k = l;
        while (i <= mid && j <= r) {
            if (array[i] <= array[j]) {
                arr[k++] = array[i++];
            } else {
                count = (count + mid - i + 1) % mod;
                arr[k++] = array[j++];
            }
        }
        while (i <= mid) {
            arr[k++] = array[i++];
        }
        while (j <= r) {
            arr[k++] = array[j++];
        }
        for (i = l; i <= r; i++) {
            array[i] = arr[i];
        }
    }

    public static void MergeSort(int l, int r, int[] array) {
        if (l < r) {
            int mid = (l + r) >> 1;
            MergeSort(l, mid, array);
            MergeSort(mid + 1, r, array);
            Merge(l, mid, r, array);
        }
    }

    public static int InversePairss(int[] array) {
        if (array == null || array.length == 0) {
            return 0;
        }
        MergeSort(0, array.length - 1, array);
        return count;
    }

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        int[] arr = {1, 2, 3, 1, 5, 6, 7, 0};
        InversePairss(arr);
    }
}

